【LeetCode 377】 Combination Sum IV 组合总和 IV

发表于 | 分类于

[LeetCode 377]Combinatiion Sum IV 组合总和 IV

Problem decription:

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:

What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

题目描述：

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

进阶：

如果给定的数组中含有负数会怎么样？
问题会产生什么变化？
我们需要在题目中添加什么限制来允许负数的出现？

Solution：

使用动态规划和递归均可，创建一个dp数组，dp[i]表示和为i的正整数组合的个数，dp[0]=1,则从i=1到target遍历，对每一个i遍历数组中每个num，若i>=num,则dp[i]+=dp[i-num],表示dp[3]=dp[2]+1 或 dp[1]+2 或 dp[0]+3,将所有情况累加就是dp[3]的结果,对原数组排序可对算法进行优化，当i<num后面则不用判断直接break。(后面给出递归版本)

Code(动态规划)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//beat 90%
class Solution {
    public int combinationSum4(int[] nums, int target) {
       int []dp=new int[target+1];
        dp[0]=1;
        Arrays.sort(nums);
        for(int i=1;i<target+1;i++){
            for(int num:nums){
                if(i<num)
                    break;
                dp[i]+=dp[i-num];
            }            
        }
        return dp[target];
    }
}

Code(递归)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//超时 
class Solution {
    
    public int combinationSum4(int[] nums, int target) {
        int count=0;
        if(target==0)
            return 1;
        for(int num:nums){
            if(target>=num)
            		count+=combinationSum4(nums,target-num); 
            }    
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//AC beat 66.7%
class Solution {
    HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
    public int combinationSum4(int[] nums, int target) {
        int count=0;
        if(target==0)
            return 1;
         if(map.containsKey(target))
             return map.get(target);
        
            for(int num:nums){
                if(target>=num)
                   count+=combinationSum4(nums,target-num); 
            }
        map.put(target,count);
        return count;
    }
}
Thanks!